
package com.leetcode.stack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * Solution20
 */
public class Solution59 {

    public static void main(String[] args) {

        Solution59 s = new Solution59();
        int[] nums = { 1, 3, 1, 2, 0, 5 };
        int k = 3;
        int[] array = s.maxSlidingWindow(nums, k);
        Arrays.stream(array).forEach(System.out::println);
    }

    public int[] maxSlidingWindow(int[] nums, int k) {

        if (nums == null) {
            return nums;
        }

        if (nums.length == 1) {
            return nums;
        }

        // 单调递增栈：
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        // 先把k-1个值入栈
        for (int i = 0; i < k; i++) {
            add(stack, nums[i]);
        }

        int[] ret = new int[nums.length - k + 1];
        for (int i = k; i < nums.length; ++i) {

            ret[i - k] = stack.peekFirst();
            if (nums[i - k] == stack.peekFirst()) {
                stack.removeFirst();
            }
            add(stack, nums[i]);

        }
        ret[nums.length - k] = stack.peek();
        return ret;

    }

    private final void add(Deque<Integer> stack, int num) {
        while (!stack.isEmpty() && stack.peekLast() < num) {
            stack.removeLast();
        }
        stack.addLast(num);
    }

}